Phá vỡ Chiều_VC

Một mô hình phân loại f {\displaystyle f} với tham số θ {\displaystyle \theta } phá vỡ một tập hợp điểm ( x 1 , x 2 , … , x n ) {\displaystyle (x_{1},x_{2},\ldots ,x_{n})} nếu với mọi cách gán nhãn dương tính/âm tính cho các điểm này, tồn tại θ {\displaystyle \theta } sao cho f {\displaystyle f} cho kết quả hoàn toàn đúng tại tất cả n điểm.

Chiều VC của mô hình f {\displaystyle f} là h ′ {\displaystyle h'} trong đó h ′ {\displaystyle h'} là số h {\displaystyle h} lớn nhất sao cho tồn tại tập hợp kích thước h {\displaystyle h} bị phá vỡ bởi f {\displaystyle f} .

Ví dụ, xét mô hình sử dụng bởi thuật toán perceptron trong không gian 2 chiều là các đường thẳng. Đường thẳng được dùng để tách rời các điểm dương tính và âm tính. Tồn tại tập hợp 3 điểm bị phá vỡ bởi mô hình này(mọi tập hợp 3 điểm không thẳng hàng đều bị phá vỡ). Tuy nhiên, không tồn tại tập hợp 4 điểm nào bị phá vỡ vì theo định lý Radon, mọi tập hợp 4 điểm đều có thể được chia thành hai tập hợp có bao lồi giao nhau. Vì vậy, chiều VC của mô hình này là 3. Dưới đây là minh họa cho 2 trong số 23 = 8 cách gán nhãn cho 3 điểm.

phá vỡ 3 điểmkhông thể phá vỡ 4 điểm